#include <iostream>
#include <map>
#include <string>

using namespace std;

map<string,string> findChain(const map<string,vector<string>> & adjacentWords, const string & first)
{
	map<string,string> previusWord;
	queue<string> q;

	q.push(first);
	while(!q.empty()){
		string current = q.front();q.pop();

		map<string,vector<string>>::const_iterator itr;
		itr = adjacentWords.find(current);
		const vector<string> & adj = itr->second;
		for(int i = 0; i<adj.size(); i++)
		{
			if(previusWord[adj[i]] == '')
			{
				previusWord[adj[i]] = current;
				q.push(adj[i]);
			}
		}
	}
	previusWord[first] = "";

	return previusWord;
}


vector<string> getChainFromPrevMap(const map<string,string>& previous,const string & second)
{
	vector<string> result;
	map<string,string> & prev = const_cast<map<string,stirng> &>(previous); 
	
}

int main()
{

}